In each of the above cited copending patent applications by the present inventor, a method and apparatus for halftone screening of images using strips of an ideal angled screen pattern to form the scan lines of a desired screen is described. Successive ideal strips are selected and assembled into a desired screen on the basis of the calculated error between the ideal screen point at the end of one strip, and the actual screen point at the beginning of the next strip. The present application relates to a general improvement in the method and apparatus for halftone screening of images. A background description of halftone image screening is set forth below.
Images are typically stored in a memory representing tone values for each pixel of the original image. For black and white image, the stored pixels represent the gray scale value corresponding to each pixel. For a color image, each color plane is stored as an array of pixels each representing the tone value for each pixel of the image in each respective color plane. For example, if each of the pixels of a black and white image is represented by a 8 bit digital word, then the tone value for a given image pixel may be one of 256 values between the black level and the white level.
Continuous tone images do not print well on most printing devices where typically the absence or presence of the ink on the paper is used to represent the printed image. In order to represent halftones (shades between the presence or absence of the printed ink), the original image is screened to produce a pattern, such as variable size dots which appear to the human eye as a halftone image.
In order to prepare a photograph for printing, it is first necessary to perform the step of halftone screening, which converts the continuous gray shades of the original into dots of varying size and shape. Typically, these dots are arranged on a regular grid of approximately 100 dots per inch. This spatial frequency is known as the screen ruling. Thus, one square inch of the final printed photograph will be composed of approximately 10,000 dots.
Screening to produce halftone images is well known. The screen consists of an array of dots, or halftone cells, each of which represents one section of continuous tone in the original image as a single dot of variable size and shape. A halftone cell, in turn, consists of an array of smaller screen pixels, or samples, each having individual values against which the input pixels derived from the original image will be compared. The individual values of the smaller screen pixels, or samples, of the repeating halftone cell which form the variable dots is referred to herein as a spot function.
The halftone screening step consists of a screen pattern generating step, and a comparison step between the input image and the screen pattern. The screen is usually stored as a fairly small pattern that repeats itself or is repeatedly generated by programming. At any point where the original image is greater than the screen pattern, the output is marked. At any point where the image is not greater than the screen pattern, the output is not marked. In other words, if the value of the image pixel is greater than corresponding value of the screen cell, a mark is generated by the marking engine, whereas if the value of the image pixel is less or equal to the screen cell value, then no mark is generated by the marking engine, or vice versa. In this way, the final screened image, composed of dots, is produced.
In color printing, there are four separate steps of halftone screening, one each for the cyan, magenta, yellow, and black inks. It is advantageous, in order to minimize objectionable moire patterns, to angle the halftone grid differently for each of the four planes. For example, the most common practice is to angle the cyan dots by 15 degrees, magenta by 75 degrees, yellow by 0 (or 90) degrees, and black by 45 degrees. If these angles are adhered to precisely, as well as the screen ruling being precisely identical for all four planes, then optimum results are achieved.
Precise screen angles can be achieved quite easily in photomechanical systems by simply rotating the photographic screen carrier. However, when the image is processed electronically, and the screened image is to be produced by a digital raster scan recording device, the problem becomes much more difficult. Rational numbers, which can be represented as the ratio of two integers, are relatively easy to accurately represent in a digital computer. Irrational numbers, which cannot be represented as the ratio of two integers, are much more difficult to accurately represent in a digital image processing device or digital computer. The tangent of a 15 or 75 degree angle is an irrational number. Therefore, screens of 15 and 75 degrees can be expected to be difficult to generate in a digital device. Also, irrational screen rulings where the number of pixels per screen cell is not a rational number ca be expected to be difficult to accurately reproduce in digital image processing device.
Prior art techniques fall into two classes. In the first class, the angles can be approximated, but not achieved precisely. These techniques are known as rational tangent angle techniques, because the screen angles are limited to arctangents of rational numbers. As a result of the inaccuracy of the screen angles and rulings, objectionable moire patterns result. A method exemplary of this technique is taught in U.S. Pat. No. 4,149,194 (Holladay). The screen pattern is represented by a strip of pixels. To generate the screen pattern, this strip is repeated across the width of the image. To angle the screen pattern, this strip is shifted by a certain number of pixels each scan line. An advantage of this technique is that it is very fast. Another advantage is the relatively modest memory requirement for the screen.
In the second class of screen generating techniques, precise angles and rulings can be achieved, but only at the cost of a large amount of computation for each pixel. This technique is described in U.S. Pat. Nos. 4,499,489 (Gall) and 4,350,996 (Rosenfeld). The device coordinate system is represented by XY space, and a halftone cell in the screen to be printed is represented by a vector in UV space, i.e. the coordinate system of the scaled and rotated screen. For each pixel, the position of the pixel in XY space is transformed into UV space. The screen pattern for that point can be determined by applying the spot function to the UV coordinates.
Although Gall and Rosenfeld describe certain speed optimizations, the disclosed technique requires many more operations per pixel than do rational angle techniques, and therefore runs considerably slower. Another technique for generating accurate screen angles is described in European Patent 0 427 380 A2 (Schiller). The Schiller patent describes a rational tangent angle method that can achieve fairly accurate screens at the cost of requiring a substantial amount of memory, typically on the order of hundreds of thousands of words.
The present invention provides a method for implementing a halftone screen pattern generation system for rotated screens including multiple angle and ruling combinations, and to produce a screened image formed with a rotated screen on a digital raster output device. In addition, the present invention provides a method of computing halftone screened images that can be implemented as a hardware circuit as well as a computer program.
Both Gall and Rosenfeld use a screen pattern consisting of screen elements arranged in a regular orthogonal array, i.e. a matrix or grid analogous to the mechanical screens used in the prior art. In accordance with a first aspect of the present invention, a screen pattern is represented in an irregular or non-grid like array of screen elements. In one embodiment, a random array of screen elements are used. In another embodiment, a Poisson-disk distribution of screen elements is used to improve quality.
In both Gall and Rosenfeld, the position of each pixel in XY space is transformed into UV space, and the screen pattern for that point is determined by applying the spot function to the UV coordinates. Typically however, there is no entry in the stored screen pattern grid of screen elements which corresponds exactly to the ideal screen point. Both Gall and Rosenfeld treat this problem by truncating (rounding downward) the coordinates of the ideal point to fit an actual screen point, regardless of the error introduced thereby. Rosenfeld indicates that individual U and/or V coordinate addresses can be rounded off (truncated) to the nearest address. Both Gall and Rosenfeld attempt to reduce the error (and loss of quality) caused by truncation, by introducing a random number to the screen memory address, which tends to disperse the resulting error throughout the screen.
In accordance with another aspect of the present invention, an actual screen point in UV space (i.e. a screen point for which an actual screen element is stored), is selected on the basis of an error calculation between the ideal screen point and the nearest actual screen points in UV space. In a specific embodiment, the length of the vector between the ideal screen point and each of the actual screen points is calculated. The smallest vector length between ideal and actual screen points represents the actual screen point selected having the minimum error. To reduce the number of necessary calculations, the four nearest points to the ideal point that succeeds each screen point are also stored in association with each entry in the stored screen pattern.
In accordance with another aspect of the present invention, the length of respective error vectors is approximated by the sum of the absolute values of the component orthogonal coordinate distances between ideal and actual screen points (instead of the typical sum of the squares calculation of vector length) thereby reducing the computational burden.
In accordance with yet another aspect of the present invention, a plurality of screen values is stored corresponding to each point in the transformed UV space. Thus, for each selected actual screen point, a plurality of screen pixels representing successive points of an ideal angled screen pattern are generated. Specifically, if 16 screen pixels of the spot function are stored for each point in UV space, then the error calculation referred to above need only be performed once for every 16 output pixels.
The method of the present invention can be practiced in a system including a scanner, an image processing device, and a raster scan output device. An original image is optoelectronically scanned and stored in memory. The image to be reproduced is divided into picture elements, or pixels, of a size suitable for halftone reproduction. On reproduction, each halftone dot is printed as a combination of smaller picture elements.
A halftone screened image is produced by (a) retrieving the pixel of the stored image pixel that corresponds to the present output pixel, (b) generating one pixel of the screen pattern, (c) comparing the image pixel and screen pixel, and (d) marking or not marking the output pixel on the basis of which was greater. The process is repeated for every output pixel. The sequence of output pixels is a raster scan, i.e. one horizontal scan line sequence of pixels followed by another horizontal scan line of pixels, which is the standard sequence for most image processing systems. The key problem solved by the present invention is to accurately generate the screen pixels in raster scan sequence.